package LeetCode;

import java.util.TreeMap;

public class LC_456_132Pattern {

    public static void main(String[] args) {

    }

    public class Solution {
        public boolean find132pattern(int[] nums) {
            TreeMap<Integer, Integer> tm = new TreeMap<>();
            for (int num : nums)
                tm.put(num, tm.getOrDefault(num, 0) + 1);
            int min = Integer.MAX_VALUE;
            for (int num : nums) {
                int cnt = tm.get(num);
                if (cnt > 1) {
                    tm.put(num, cnt - 1);
                } else {
                    tm.remove(num);
                }
                if (num <= min) {
                    min = num;
                } else {
                    Integer target = tm.higherKey(min);
                    if (target != null && target < num) {
                        return true;
                    }
                }
            }
            return false;
        }

    }
}